import java.util.*;

/**
 * @author LKQ
 * @date 2022/3/26 20:22
 * @description DFS利用hash表保存访问过的点，防止进入死循环
 */
public class Solution {
    public static void main(String[] args) {

    }
    private Map<Node, Node> visited = new HashMap<>();

    public Node cloneGraph(Node node) {
        if (node == null) {
            return node;
        }
        // 如果该节点已经被访问了，那么取出对应的克隆节点
        if (visited.containsKey(node)) {
            return visited.get(node);
        }
        // 克隆节点，注意到为了深拷贝不会克隆它的邻居的列表
        Node cloneNode = new Node(node.val, new ArrayList<>());

        visited.put(node, cloneNode);

        // 遍历该节点的邻居并更新克隆节点的邻居列表
        for(Node node1 : node.neighbors) {
            cloneNode.neighbors.add(cloneGraph(node1));
        }
        return cloneNode;
    }
}
class Node{
    public int val;
    public List<Node> neighbors;

    public Node(){
        this.val = 0;
        this.neighbors = new ArrayList<>();
    }
    public Node(int val) {
        this.val = val;
        neighbors = new ArrayList<>();
    }
    public Node(int val, List<Node> neighbors) {
        this.val = val;
        this.neighbors = neighbors;
    }
}